﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;
using System.Runtime.InteropServices;

using alib.Debugging;

namespace agree
{
	public abstract partial class ChartControl<T, W> : ChartResources<W>
		where T : ChartControl<T, W>
		where W : struct, IProximalContext<W>
	{
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Accept new edges into the chart. Atomically with insertion into the chart, stamp the edge with an interlocking
		/// sequence barrier in order to separate interested parties into two groups: those who registered previously--and 
		/// who will receive the edge now, versus those who register at any point afterwards, who will receive the edge via 
		/// the retroactive edge delivery mechanism which is part of the subscription process.
		/// </summary>
		/// <remarks>
		/// We check subsumption before making the new passive edge visible ('active'), because if proactive packing is 
		/// performed we don't want to deal with the complications of having the edge ever having been published. The 
		/// purpose of putting the edge in the chart at all, however, as we just did, is so that anyone who tries to determine 
		/// sequencing relative to this edge will be blocked from proceeding further up the chart cell until this
		/// subsumption check is complete. The bloking ensures deterministic correctness of maximal packing: the global 
		/// sequencing system is used to partition edges within a cell for the purposes of evaluating 
		/// subsumption. In this case, since the objects under comparison are within the same list (unlike the passive-to-
		/// active edge subscription mechanism), and the operation (subsumption checking) is commutative, we only need to 
		/// evaluate within the lower partition.
		/// </remarks>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public unsafe IDisposable AddObj(System.Reactive.Concurrency.IScheduler sch, IChartObj<W> po)
		{
			begin();

			if (TerminationRequested)
				goto exit;

			/// add passive edge to chart
			AddChartObj(po);

			/// record the passive edge
			Interlocked.Increment(ref c_pass);

#if DEBUG
			/// now that there's a sequence ID, print out some stuff
			var pctrl = this as ParseControl;
			if (pctrl != null)
			{
				if (pctrl != null && SysObj.Instance.tw_debug != null)
					pctrl.ChartEdgeReport((IChartObj<ChartSpan>)po);
			}
#endif

			IPacking ppo;
			if ((ppo = po as IPacking) != null && new _packing_helper(this, ppo).SubsumptionPacking())
			{
#if DEBUG
				Debug.Assert(ppo.IsHoldOrRemove());
#endif
				goto exit;
			}

			/// make the new edge visible
			po.EndTransact(AtomicSeqState.Available);

			/// a task for generating new rules
			StartTask(TryEligibleRules, po);

			SendToPassiveEdges(po);

		exit:
			end();
			Release();
			return EmptyDisposable.Instance;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Generate new activities for the specified IChartObj
		/// Try to unify the given chart edge against the KEY position of each compatible rule. If successful, proceed as 
		/// follows:
		/// - Unary rules are now finished up immediately here, creating a passive edge (without creating an ActiveEdge)
		/// and entering it into the parse chart.
		/// - Otherwise, an ActiveEdge that expands leftwards or rightwards is created, as appropriate. Active edges are 
		/// always seeded with a positioned passive edge, but note that neither this partial passive edge (nor the
		/// ActiveEdge) are ever entered into the parse chart. Instead, this function uses a subscription mechanism
		/// to register the active edge's interest in a particular chart position. This subscription is what keeps the 
		/// ActiveEdge (object) alive.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		protected unsafe IDisposable TryEligibleRules(System.Reactive.Concurrency.IScheduler sch, IChartObj<W> cur_obj)
		{
			bp("Try new rules", cur_obj);
			if (!cur_obj.WaitActive())
				goto exit;

			begin();

			Rule r_dtr = cur_obj.ChartLicense as Rule;

			bool f_has_grammar_rule = this is GenControl && cur_obj.LicensesApplied().Any(r => r is SyntaxRule);
			bool f_rightwards = true;
			int i_key = 0;
			IChartObj[] cur_unary = null;

			foreach (IActiveRule ir in rules)
			{
				Rule rule = ir.BaseRule;

				if (f_has_grammar_rule && rule is LexicalRule)
					continue;
#if false
				/// No, this blocks all 6 realizations for "Cats like girls that like boys." (0x70FB3DC11C9CDB74)
				if (this is GenControl && cur_obj.LicensesApplied().Any(app => app == base_rule))
					continue;
#endif
				/// Note: generator needs access to the skolemized rule and computes 'new_coverage' from scratch on every call.
				/// The parser does not modify 'new_coverage'

				W new_coverage = cur_obj.ProximalContext;
				if (!CheckRuleGeometry(ir, ref new_coverage))
				{
					//ctrl.c_stats(ip => ((Stats._chart*)ip)->EdgeGeometryFiltered());
					continue;
				}

				/// Rule pre-check filter "A Bag of Useful Technique for Efficient and Robust Parsing" (Kiefer et al. 1999)
				if (r_dtr != null && !r_dtr.IsCompatibleKeyMother(rule))
				{
					//ctrl.c_stats(ip => ((Stats._chart*)ip)->RuleFiltered());
					continue;
				}

				TfsSlot daughter;
				TfsSlot[] rd = ir.DaughterNodes;
				int rule_arity = rd.Length;

				if (rule_arity == 1)
				{
					daughter = rd[0];
				}
				else
				{
					i_key = rule.KeyDaughterIndex;

					/// We only have to try out one of the rule's ARGS positions and it doesn't matter which one it is,
					/// as long as that choice is consistently used for that rule. This allows us to choose the KEY arg 
					/// without the risk of doing double work. Usage of this new edge in the other alignments may be 
					/// handled later, when/if the rule succeeds in a neighboring chart position.
					if (i_key == 0)
					{
						daughter = rd[0];
						f_rightwards = true;
					}
					else
					{
						daughter = rd[rule_arity - 1];
						f_rightwards = false;
					}
				}

				/// Quick-check:
				/// Robert Malouf, John Carroll, Ann Copestake. 2000. Efficient feature structure operations without compliation.
				///		Natural Language Engineering 6 (1): 29-46. Cambridge: Cambridge University Press
				/// todo: track which qc rules failed for this rule daughter and propagate to the next rule..?
				if (qc != null && qc._QuickCheck(cur_obj.Tfs, daughter.tfs, daughter.out_mark))
					continue;

				Tfs.Flags opts = unify_opts;
				if (rule_arity == 1)
					opts |= Tfs.Flags.DeleteArgs;

				ArrayTfs new_mother = u.UnifySection(daughter, cur_obj, opts);
				Interlocked.Increment(ref c_unif);
				if (new_mother == null)
					continue;
				new_mother._set_trace(this);

				if (cur_unary == null)
					cur_unary = new[] { cur_obj };

				if (rule_arity == 1)
					ProcessCompletedRule(rule, new_mother, cur_unary, new_coverage);
				else
					AddActiveEdge(new ActiveEdge(f_rightwards, this, (SyntaxRule)rule, new_mother, cur_unary, new_coverage));
			}

			end();
		exit:
			Release();
			return EmptyDisposable.Instance;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// When a rule has successfully completed building all of its structure, create a new passive edge.
		/// If it spans the chart, try to match a start symbol.
		/// But note that spanning roots are not exempt from further rule evaluation.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		protected void ProcessCompletedRule(Rule rule, ArrayTfs tfs, IReadOnlyList<IChartObj> rgo, W cxc)
		{
			if (!CheckPassiveAccessibility(tfs, ref cxc))
				return;

			IChartObj nce = null;

			if (cxc.CoverageCount == spanning_count)
			{
				StartSymbol[] ss_matches;
				Interlocked.Increment(ref c_span);
				if ((ss_matches = CheckStartSymbols(tfs)) != null)
				{
					var ird = CreateChartObj(rule, tfs, rgo, cxc, ss_matches);
					lock (forest)
						forest.Add(ird);
					nce = ird;
				}
			}
			StartTask(AddObj, (IChartObj<W>)(nce ?? CreateChartObj(rule, tfs, rgo, cxc, null)));
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		unsafe StartSymbol[] CheckStartSymbols(ArrayTfs tfs)
		{
			StartSymbol[] arr = null;

			for (int i = 0; i < rgss.Length; i++)
			{
				var start_sym = rgss[i];

				if (u.UnifyCheck(start_sym.Expanded, tfs))
				{
					alib.Array.arr.Append(ref arr, start_sym);
#if !CHECK_ALL_SS
					/// If not packing, stop checking start symbols after a first match.
					if (pack_opt == 0)
						break;
#endif
				}
			}
			return arr;
		}

#if EQUIVALENT_EDGES
		public List<alib.Enumerable.Pairing<ArrayTfs>> eq_tfs = new List<alib.Enumerable.Pairing<ArrayTfs>>();
#endif

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Check for a subsumption relationship between a newly derived edge and any of the existing co-spanning edges.
		/// Proactive packing occurs when the existing edge subsumes the new edge, or when they subsume each other (which
		/// means they are identical). Retroactive packing occurs when the new edge subsumes the existing edge. There are
		/// two other possibilities: that there is no overall subsumption relationship between otherwise compatible edges, 
		/// or that the two are incompatible (do not unify). Fortunately, no packing is indicated in either case, because 
		/// if we had to distinguish between these two cases, the subsumption test would be much less efficient (it would
		/// have to resolve coreference chains).
		/// </summary>
		/// <reference>
		/// Stephan Oepen, John Carroll. 2000. "Ambiguity Packing in Constraint-based Parsing--Practical Results."
		/// In Proceedings of the 1st North American chapter of the Association for Computational Linguistics 
		/// conference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 162-169. 
		/// </reference>
		/// <remarks>
		/// derived parents of packed edges automatically become defunct (not 'active'). Since only packed
		/// edges can be in the 'hold' state, any edge that has a daughter in the 'hold' state can be
		/// ignored; this is achieved by incrementing a global generation count which
		/// immediately invalidates all of these states, which are cached, causing any still 'active' chart edge 
		/// to re-evaluate this condition regarding itself, on demand, at such time as it's queried. Now since we 
		/// are in the parsing phase, the fact that we just put an object in the 'hold' state doesn't affect any 
		/// of these parent/daughter results ('hold' does not entail 'defunct') but what does make a difference 
		/// is the transfer of the packed edges from the old edge to the new, as the _daughters_ of the old edge 
		/// may now--or at such future time as they become defunct--cause the deactivation of their altered
		/// derivation list.
		/// </remarks>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		struct _packing_helper
		{
			ChartControl<T, W> ctrl;
			IPacking new_edge;
			IPacking[] deferred_retro;

			bool f_pack_exact;
			bool f_entire_span;
			sbyte pack_opt;

			public _packing_helper(ChartControl<T, W> ctrl, IPacking new_edge)
			{
				this.ctrl = ctrl;
				this.new_edge = new_edge;
				this.f_pack_exact = ctrl.f_pack_exact;
				this.f_entire_span = ctrl.IsSpanning(new_edge);
				this.pack_opt = ctrl.pack_opt;
				this.deferred_retro = null;
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// 
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			public bool SubsumptionPacking()
			{
#if DEBUG && false
				var ne = new_edge;
				var arr = alib.Enumerable._enumerable_ext.ConsumeEnumerator(ctrl.ItemEdges(ne.ProximalContext))
					.Select(o => String.Format("{0,5}{1} {2:X8} {3} {4} {5}",
						o.Id,
						o == ne ? "*" : " ",
						o.GetHashCode(),
						o.StatusCode,
						o.ProximalContext.ToString(),
						o.ChartLicense.Name))
					.ToArray();
#endif
				if (check_all(ctrl.GetPackingCandidates(new_edge)))
					return true;

				if (deferred_retro != null)
					retry_deferrals();

				return false;
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// 
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			bool check_all(IEnumerator<IChartObj> e)
			{
				IPacking existing;

				while (e.MoveNext())
					if ((existing = e.Current as IPacking) != null)
						if (check_edge(existing))
							return true;
				return false;
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// 
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			bool check_edge(IPacking existing)
			{
#if DEBUG
				if (existing == new_edge)
					throw new Exception();

#endif
				/// Don't permit a spanning edge which didn't match a start symbol (i.e. Derived)
				/// to be packed into one that did (i.e. Completed), nor vice-versa.
				if (f_entire_span && new_edge.HasRootMatches() != existing.HasRootMatches())
					return false;

				/// Since we have our sequence number reserved already, we know that the id of any id-pending node,
				/// when assigned, will be larger than ours so therefore 'new_edge' is not responsible for evaluting it
				if (existing.Id == 0)
					return false;

				if (existing.IsHoldOrRemove())
					return false;

				/// 'new_edge' is only responsible for evaluating packing against edges with a lower sequence identifier.
				if (!existing.SeqIdBelow(new_edge.Id))
				{
					/// the code below shows that the edges are not necessarily ordered by Id, so 'break' is not indicated
#if false 
					long i0 = existing.Id, i1;
					while (e.MoveNext())
						if ((i1 = e.Current.Id) != 0 && i1 < new_id)
							throw new Exception();
					break;
#else
					return false;
#endif
				}

				using (ctrl.suspend_timing)
					if (!existing.WaitActive())
						return false;

				/// evaluate the subsumption relationship between two TFSen
				int sr = Subsumption.Check(ctrl.rr.r_pack, existing, new_edge);

				//if (sr == 3)
				//{
				//	var ssr = Subsumption.Check(ctrl.rr.r_none, existing, new_edge);
				//	if (DerivationComparer.Instance.Equals(existing, new_edge))
				//		Nop.X();
				//	else
				//		Nop.X();
				//}
#if EQUIVALENT_EDGES
				if (sr == 3)
				{
					lock (ctrl.eq_tfs)
						ctrl.eq_tfs.Add(new alib.Enumerable.Pairing<ArrayTfs>(existing, new_edge));
				}
#endif

				/// evaluate desired packing modes
				if ((sr & pack_opt) == 0 || (f_pack_exact && sr != pack_opt))
					return false;

				if ((sr & Subsumption.FirstSubsumesSecond) != 0)
				{
					/// proactive packing (the existing edge subsumes or is equivalent to the new edge)

					if (Proactive(existing))
					{
						if ((sr & Subsumption.SecondSubsumesFirst) != 0)
							Interlocked.Increment(ref ctrl.c_pack_eq);
						else
							Interlocked.Increment(ref ctrl.c_pack_fwd);
						return true;
					}
				}
				else if (sr == Subsumption.SecondSubsumesFirst)
				{
					/// retroactive packing (the new edge subsumes the existing edge)
					/// if a retroactive edge is busy, make a note of it to try again later

					if (existing.State() == AtomicSeqState.Available)
						Retroactive(existing);
					else if (!existing.IsRemove())
						alib.Array.arr.AppendSafe(ref deferred_retro, existing);
				}
				return false;
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// put the new, unpublished edge on HOLD before being added to the packing list, so 
			/// that it can be never witnessed as active in any context
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			bool Proactive(IPacking existing)
			{
				using (ctrl.suspend_timing)
					if (!existing.BeginTransact())
						return false;

				new_edge.EndTransact(AtomicSeqState.Hold);

				existing.HoistPackingFrom(new_edge);

				existing.EndTransact(AtomicSeqState.Available);

				return true;
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// 
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			void Retroactive(IPacking existing)
			{
				using (ctrl.suspend_timing)
					if (!existing.BeginTransact())
						return;

				/// our claim is secure; release lock on 'old' as quickly as possible
				existing.EndTransact(AtomicSeqState.Hold);

				new_edge.HoistPackingFrom(existing);

				Interlocked.Increment(ref ctrl.c_pack_rev);
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// Try to complete the retroactive packing for edges that were blocked earlier
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////
			void retry_deferrals()
			{
				IPacking existing, last;
				int cc, i, c = deferred_retro.Length;
				do
					for (i = cc = 0, last = null; i < c; i++)
						if ((existing = deferred_retro[i]) != null)
						{
							switch (existing.State())
							{
								case AtomicSeqState.Transact:
									last = existing;
									cc++;
									continue;
								case AtomicSeqState.Available:
									Retroactive(existing);
									break;
								case AtomicSeqState.Hold:
								case AtomicSeqState.Remove:
									break;
							}
							deferred_retro[i] = null;
						}
				while (cc > 1);

				if (last != null)
					Retroactive(last);
			}
		};
	};
}
